package leetcode.toend;

public class T1894 {
    class Solution {
        public int chalkReplacer(int[] chalk, int k) {
            int n = chalk.length - 1;
            long[] res = new long[chalk.length];
            res[0] = chalk[0];
            for (int i = 1; i < chalk.length; i++) {
                res[i] = res[i - 1] + (long) chalk[i];
            }
            long t = k % (res[n]);
            for (int i = 0; i < chalk.length; i++) {
                if (res[i] > t) {
                    return i;
                } else {
                    continue;
                }
            }
            return 0;
        }
    }
    class Solution2 {
        public int chalkReplacer(int[] chalk, int k) {
            int n = chalk.length;
            if (chalk[0] > k) {
                return 0;
            }
            for (int i = 1; i < n; ++i) {
                chalk[i] += chalk[i - 1];
                if (chalk[i] > k) {
                    return i;
                }
            }

            k %= chalk[n - 1];
            return binarySearch(chalk, k);
        }

        public int binarySearch(int[] arr, int target) {
            int low = 0, high = arr.length - 1;
            while (low < high) {
                int mid = (high - low) / 2 + low;
                if (arr[mid] <= target) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low;
        }
    }
}
